package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

import java.util.*;

/**
 * @author By ZengPeng
 */
public class 力扣_46_全排列 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_46_全排列().permute(new int[]{1,2,3}));
        System.out.println(new 力扣_46_全排列().permute(new int[]{0,1}));
        System.out.println(new 力扣_46_全排列().permute(new int[]{1}));
        System.out.println(new 力扣_46_全排列().permute(new int[]{1,2,3,4,5,6,7,8,9}));
    }

    /**
    题目：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。
     你可以 按任意顺序 返回答案。

     示例 1：
     输入：nums = [1,2,3]
     输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

     示例 2：
     输入：nums = [0,1]
     输出：[[0,1],[1,0]]

     示例 3：
     输入：nums = [1]
     输出：[[1]]

     提示：
     1 <= nums.length <= 6
     -10 <= nums[i] <= 10
     nums 中的所有整数 互不相同

    分析：【P 🧡💛💙】
       1.回溯法 【排列：需要位图记录是否已使用元素】，使用list存储已经存在的数，重新cntains一下，在判断是否要递归
             1.一条路走到黑
             2.回退一步
             3.另寻他路

        难点：如何判断当前值已经存在？ 我开始使用的是list存储元素，用了就删除，用完就add回来
        优化：使用 boolean[]  存储true false 表示使用过没

    边界值 & 注意点：
       1.
     **/
    public List<List<Integer>> permute(int[] nums) {
        //2.使用 boolean[]  存储true false 表示使用过没
        List<List<Integer>> res = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        boolean[] used = new boolean[nums.length];
        recursive(nums,used, stack, res);
        return res;

      //1.直接判断是否存在
        /*List<List<Integer>> res = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        recursive1(nums, stack, res);
        return res;*/
    }

    private void recursive1(int[] nums, Stack<Integer> stack, List<List<Integer>> res) {
        if(stack.size()==nums.length){
            res.add(new ArrayList<>(stack));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(!stack.contains(nums[i])){
                stack.push(nums[i]);
                recursive1(nums, stack, res);
                stack.pop();
            }
        }
    }

    /**
     *  回溯 1,2,3
     * @param  nums  目标数组
     * @param  used 记录使用过没
     * @param  stack 前面已经加入的节点
     * @param  res  结果集合
     **/
    private void recursive(int[] nums, boolean[] used, Stack<Integer> stack, List<List<Integer>> res) {
        if(stack.size()==nums.length){
            res.add(new ArrayList<>(stack));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(!used[i]){
                stack.push(nums[i]);
                used[i] =true;
                recursive(nums,used, stack, res);
                used[i] =false;
                stack.pop();
            }
        }
    }

    /**
    *  回溯 1,2,3
     * @param  list  目标数组
     * @param  stack 前面已经加入的节点
     * @param  res  结果集合
     **/
    public void recursive2(List<Integer> list,  Stack<Integer> stack, List<List<Integer>> res){
        if(list.isEmpty()){
            res.add(new ArrayList<>(stack));
            return;
        }
        for (int i = 0; i < list.size(); i++) {
            Integer num = list.get(i);
            stack.push(num);
            list.remove(num);
            recursive2(list, stack, res);
            list.add(i,num);
            stack.pop();
        }
    }
}
